第5章 连通度·匹配·网络流

第5章 连通度·匹配·网络流5.1 连通度(无向图)5.1.1 割点,割边和块5.1.2 连通度5.2 二部图的匹配5.2.1 匹配5.2.2 二部图的匹配5.3 网络流(netflow)5.3.1 实际背景5.3.2 一些定义(网络,可行流,饱和边,最大流,割切)5.3.2 Edmonds-Karp Algorithm5.3.2.1 算法5.3.2.2 时间复杂度证明5.3.2.2.1 概念引入5.3.2.2.2 引理15.3.2.2.3 引理25.3.2.2.4 引理35.3.2.2.5 定理5.4 作业5.5 参考答案

5.1 连通度(无向图)

5.1.1 割点,割边和块











5.1.2 连通度















5.2 二部图的匹配

5.2.1 匹配



5.2.2 二部图的匹配













5.3 网络流(netflow)

5.3.1 实际背景

5.3.2 一些定义(网络,可行流,饱和边,最大流,割切)









5.3.2 Edmonds-Karp Algorithm

5.3.2.1 算法


5.3.2.2 时间复杂度证明

5.3.2.2.1 概念引入


5.3.2.2.2 引理1



5.3.2.2.3 引理2



5.3.2.2.4 引理3



5.3.2.2.5 定理



5.4 作业

 

5.5 参考答案